home *** CD-ROM | disk | FTP | other *** search
/ 501 Great Games / 501 Great Games - Volume One (2001)(Guildhall Leisure Services).iso / SPAN-IT! / HELP.TXT < prev    next >
Text File  |  1993-06-30  |  15KB  |  422 lines
  1. The information in this file is the non-formatted version of the
  2. Windows 3.1 (tm) Help File.
  3.  
  4.     Object of the Game
  5.     What are Personalities?
  6.     Registration
  7.     Basic Personality Concepts
  8.     Personality Factor Definitions
  9.     About the Author
  10.     The #1 Beta Man
  11.  
  12. ***
  13. Object of the Game
  14. ***
  15.  
  16. Span-It! is a two-player connect-the-dot game.  Each player is 
  17. assigned an orientation at the start of the game.  One player 
  18. is horizontal and the other is vertical.  Players alternate turns 
  19. placing connectors on the board.  The object of the game is 
  20. for each player to span the board in the direction of his/her 
  21. favored orientation by completing a path from one end to 
  22. another.
  23.  
  24. The challenge is to block your opponent while still making 
  25. progress.  A game will never end in a draw.  Someone always 
  26. wins (or quits!)
  27.  
  28. By default, Span-It! assumes the horizontal player is human, 
  29. and the vertical player is the computer using a default 
  30. personality.  Any combination of human and computer 
  31. players is allowed.
  32.  
  33. ***
  34. What are Personalities?
  35. ***
  36.  
  37. Span-It! has an exciting option that is not available in many 
  38. games.  Not only is it possible to play against the computer, 
  39. but you may define virtually every aspect of how the 
  40. computer plays.  
  41.  
  42. Like many game playing programs, Span-It! assigns a 
  43. number to the perceived importance of every empty position 
  44. on the game board.  This number is called the weight.   The 
  45. board position (node) with the best weight is the one Span-It! 
  46. will select for the next move.
  47.  
  48. The computer assigns the weights based on a well-defined 
  49. set of factors.  For example,  Span-It! will add the value of the 
  50. PathIsWinner factor to the weight of an empty position that 
  51. can win the game.  There are several factors  that influence 
  52. the weight of a node.  
  53.  
  54. A personality is a set of values assigned to the factors used 
  55. by the computer during auto-play mode.  When you press 
  56. one of the "Load Personality" buttons in the new game dialog 
  57. box, you may select different personalities.  Some 
  58. personalities are more "intelligent" than others.  You also may 
  59. edit or create your own.
  60.  
  61. Remember that personalities only influence the way the 
  62. computer plays.  Human players probably use different 
  63. methods to "calculate" moves.  The selected personality for a 
  64. human player is the one that the HINT menu option uses.  
  65. The way to tell the computer to play instead of a human is by 
  66. checking the "computer plays" box in each player definition 
  67. section of the new game dialog box.
  68.  
  69. It is possible to have the computer play itself using two 
  70. different personalities.  The "referee" is a completely different 
  71. part of the program.  The opposing personalities are not 
  72. allowed to cheat!
  73.  
  74. ***
  75. Registration
  76. ***
  77.  
  78. Span-It! 
  79. Copyright (c) 1993, Mark T. Chapman
  80. All Rights Reserved
  81.  
  82. Span-It! is shareware.  You may try the program free of charge and may 
  83. make copies for others.  If you continue to play Span-It!, a $15 
  84. registration fee is required.  This program may be distributed freely or for 
  85. a nominal media charge (less than $5) provided that no modifications 
  86. are made to any files. Authenticity may be verified for free by the 
  87. program's author via. SASE for a limited time.  For registration 
  88. information, see the file REGISTER.TXT or REGISTRATION under the 
  89. HELP menu.
  90.  
  91. THE PROGRAM IS PROVIDED "AS-IS". NO WARRANTIES OF ANY 
  92. KIND, EXPRESS OR IMPLIED,  ARE MADE AS TO IT OR ANY 
  93. MEDIUM IT MAY BE ON.  NO REMEDY IS PROVIDED BY THE 
  94. AUTHOR FOR INDIRECT, CONSEQUENTIAL, PUNITIVE OR 
  95. INCIDENTAL DAMAGES ARISING FROM IT, INCLUDING SUCH FROM 
  96. NEGLIGENCE, STRICT LIABILITY, OR BREACH OF WARRANTY OR 
  97. CONTRACT, EVEN AFTER NOTICE OF THE POSSIBILITY OF SUCH 
  98. DAMAGES.  
  99. USE AT YOUR OWN RISK.
  100.  
  101. For $15 registration (plus shipping) you will receive:
  102.  
  103. 1. Your own personalized copy of this and the next release 
  104. of Span-It!
  105. 2. Prototypes of Span-It! on alternate operating systems.
  106. 3. The Span-It! Toolkit. Several programs that will help you 
  107. create better personalities.
  108. 4. One entry per person in the free Span-It!  Ultimate 
  109. Personality Competition. (Registration is not required to 
  110. enter the competition.  Just mail a disk or printout of your best 
  111. Span-It! personality to the registration address below.  
  112. Winning personalities will be included in the next release of 
  113. Span-It!)
  114.  
  115. Registration Forms can be printed via. the help screen (FILE | 
  116. PRINT TOPIC) or else you may copy the file REGISTER.TXT 
  117. to the printer from DOS by:   
  118.  
  119. C:\SPANIT\> COPY REGISTER.TXT PRN:
  120.  
  121. Please send registration of $15 U.S. (plus $2 shipping in 
  122. Continental United States, $5 elsewhere) to:
  123.  
  124. Mark Chapman
  125. Span-It! Registration
  126. 1126 Wauwatosa Rd.
  127. Cedarburg, WI 53012
  128.  
  129. Your name and shipping address:
  130.  
  131. Media type (3.5" or 5.25" floppy disk):
  132.  
  133. Your Span-It! handle (the name to appear on the 
  134. personalized "About" screen):
  135.  
  136.  
  137.  
  138. Don't forget to enter your best personality in the Span-It!  
  139. Ultimate Personality Competition.
  140.  
  141. For academic discussion, my Internet address is 
  142. chapman@miller.cs.uwm.edu.
  143.  
  144. Your suggestions are always welcome.
  145.  
  146. Watch for the I.B.M. OS/2 2.1 version soon! 
  147.  
  148. Thank You for trying my game.  
  149.  
  150. ***
  151. Personality Factor Descriptions
  152. ***
  153.  
  154. Before reading this section, please make sure you are familiar 
  155. with the material in Basic Personality Concepts
  156.  
  157. This is a step-by-step description of how the value of a trial 
  158. node is computed.  Part A describes how the weight of a 
  159. single trial node is computed.  Part B describes how all trial 
  160. nodes on the board are compared to select the best move.
  161.  
  162. Part A: Compute the weight of a single trial node
  163.  
  164. 1.  Determine the initial weight of the trial node.
  165.  
  166. NodeMajor:  If the trial node is a major node, assign 
  167. NodeMajor to the initial weight of the trial node. 
  168.  
  169. NodeMinor:  If the trial node is minor node, assign 
  170. NodeMinor to the initial weight of the trial node.
  171.  
  172. NodeRandom:  Always add a random number between 0 
  173. and NodeRandom to the weight of the trial node.
  174.  
  175. 2. Add the change in path weight to the weight of the trial 
  176. node.
  177.  
  178. The path weight may be computed for any Path.  It does not 
  179. matter if the path is a Real Path or a Resultant Path.  All we 
  180. care about are the characteristics of the connected set of 
  181. nodes.  The order the nodes were connected will not change 
  182. the path weight.
  183.  
  184. A path weight PW is computed as follows:
  185.  
  186. PathMajorSpan:  Assign variable PS to the number of rows 
  187. or columns the path spans in the major direction.  Assign 
  188. the initial path weight to: 
  189.     PW = (Sign of PathMajorSpan) * (AbsoluteValue of 
  190. PathMajorSpan)^PS.  
  191.  
  192. PathMinorSpan:  Assign variable ps to the number of rows 
  193. or columns the path spans in the minor direction. Add the 
  194. PathMinorSpan factor into the path weight by the following 
  195. formula:
  196.     PW = PW + (Sign of Path Major Span) * (Absolute 
  197. Value of PathMinorSpan)^ps.
  198.  
  199. PathIsAnchored:  If the path is connected to a major edge, 
  200. add PathIsAnchored to the value of PW.  (Note: If a path is 
  201. anchored at two opposite major edges, the path is a 
  202. winner).
  203.     if the path is connected to a major edge, 
  204.         PW = PW + PathIsAnchored
  205.  
  206. PathIsWinner:  If a path spans the board in the major 
  207. direction, add PathIsWinner to W.  (The value of 
  208. PathIsWinner usually is very large compared to every 
  209. other factor.)
  210.     If the path wins the game
  211.         PW = PW + PathIsWinner
  212.  
  213. PathMemberCount:  Assign M to the total number of nodes 
  214. in a path.
  215.     PW = PW + PathMemberCount ^M .
  216. Now that we know how to compute the weight of a path, let's 
  217. see how path weight influences the value of the trial node.
  218. A.  Identify the real paths that the current player owns that are 
  219. adjacent to the trial node.
  220. B.  Compute the Existing Path Weight (EPW) as the sum of 
  221. the PW of the paths identified in (A).
  222. C.  Generate the resultant path.
  223. D.  Compute the Resultant Path Weight (RPW).
  224. E.  Add the change in path weight (RPW minus EPW) to the 
  225. weight of the trial node.
  226. 3.  Add the change in board weight to the weight of the trial 
  227. node.
  228. BoardPathCount:  Assign np = the number of new paths 
  229. created by selecting the trial node.
  230. NP = 1    (When a new path is started)
  231. NP = 0    (When an existing path is expanded)
  232. NP = -1   (When two paths are merged)
  233.  
  234. Now add NP times BoardPathCount to the trial node 
  235. weight.
  236. Part B:  How all trial nodes are compared to select the 
  237. next best move
  238. GamePredictability%:  Let MyW = value of selecting the trial 
  239. node.  Let YourW = weight if the auto-player uses the 
  240. current personality to assess the value if the other player 
  241. were to select the trial node.  (The referee does not allow 
  242. "cheating".  To calculate YourW, the auto-personality has 
  243. to use its own weights.)  The final value W of the trial 
  244. node is computed by:
  245. W = MyW + (GameTreePredictability% * YourW) / 100
  246.  
  247. GameTreeMaxBreadth:  The computer attempts to "look 
  248. ahead" a certain number of moves to help decide the 
  249. weight of each free node. It could take a very long time to 
  250. evaluate every possible outcome of a single game.   
  251. GameTreeMaxBreadth is the factor that limits the breadth 
  252. of the beam search used for the game tree. 
  253.  
  254. GameTreeMaxDepth:  GameTreeMaxDepth is the maximum 
  255. number of moves ahead the computer looks.  KEEP THIS 
  256. VALUE SMALL.  The total number of moves that the 
  257. computer will look at has an upper bound of:
  258. GameTreeMaxBreadth ^ GameTreeMaxDepth
  259. abbreviated to: b  ^ d.
  260.  
  261. A 486-33 can compute about 1,000 moves in a 
  262. reasonable amount of time.  2,000 moves takes about 
  263. twice as long.  The important thing to realize is that the 
  264. number of moves is exponential with respect to d.  If b = 
  265. 10 and d = 3, the computer already will examine up to 
  266. 1,000 moves per turn.  If you let b = 10 and d = 6, the 
  267. computer will examine up to 1,000,000 moves per turn!
  268. Let b and d remain small!  Otherwise the computer will 
  269. just take to much time to respond.  It will be interrupted at 
  270. the Maximum Auto Move time; thus, the personality will 
  271. not get a chance to finish the calculations anyway!
  272.  
  273. GameTreeBreadthTrim%:  In addition to the maximum auto 
  274. move time function, each personality has an option to trim 
  275. or increase the breadth of the search as it descends levels 
  276. in the game tree.  It is most likely that you would want this 
  277. factor to be a positive number.  Otherwise the breadth at 
  278. each level will increase and the time to select a move will 
  279. grow very quickly.
  280.  
  281. GameTreeValueFade%:  If you read this far, you deserve to 
  282. find out that the personalities don't really use an actual 
  283. "game tree" to look ahead moves.  I made my own 
  284. algorithm to allow experimentation into how important the 
  285. value of the perceived weights change as we look deeper 
  286. into the game tree.  This factor is used to fade or increase 
  287. the value of the possible moves when looking ahead.  It is 
  288. applied as the values are passed back up each level.  A 
  289. positive value means that the value of each level 
  290. decreases based on the level of the game tree.  
  291.  
  292.  
  293. ***
  294. Basic Personality Concepts
  295. ***
  296.  
  297. The information in this section is crucial to the understanding 
  298. of the Factor Definitions,  It is assumed that you have played 
  299. a few games of Span-It!  It may be helpful to examine the 
  300. Board Diagram.
  301.  
  302. Vocabulary:
  303.  
  304. Node
  305. Major Node
  306. Minor Node
  307. Orientation
  308. Owner
  309. Path
  310. Trial Node
  311. Resultant Path
  312. Real Path
  313. Path Major Span
  314. Path Minor Span
  315.  
  316. ***
  317. About the Author 
  318. ***
  319.  
  320. Education:
  321.  
  322. Bachelor of Science University of Wisconsin, Milwaukee 
  323. 1992 (Computer Science.)
  324. Programmed in C and C++ in a UNIX environment.
  325. Worked on a wide variety of projects, including parallel 
  326. processing and infinite precision arithmetic.
  327. Currently a graduate student at UWM studying Cryptography 
  328. and Data Security.
  329.  
  330. Work Experience Overview:
  331.  
  332. Worked at least five years at a local consulting firm.  
  333. Managed projects and coordinated personnel.
  334. Supplied primary customer contact for several major 
  335. accounts.
  336. Prepared and presented custom sales and training seminars.
  337. Designed and programmed a wide range of applications.
  338. Developed software for UNIX, DOS, WANG VS and other 
  339. operating systems.
  340. Programmed in C, COBOL, Paradox(TM), Informix(TM), and 
  341. more.
  342. Helped install and administer Novell(TM), LanTastic(TM), 
  343. and UNIX Networks.
  344. Distributed data collection applications with hand-held 
  345. computers.
  346. "Downsized" several operations from old minicomputers to 
  347. UNIX or PC's.
  348.  
  349. Self-study highlights:
  350.  
  351. Artificial intelligence and game playing.
  352. Windows 3.x (tm) API (obvious!)
  353. OS/2 (tm) PM Programming (Span-It! is on the way...)
  354.  
  355. ***
  356. Thank You
  357. ***
  358.  
  359. A quick thanks to my good friend, Jay Dittmann.   
  360. His persistence and detailed criticism pushed the limits of his 
  361. free time, my compiler, our modems,  
  362. and most wonderfully -- the quality of the final product.
  363.  
  364.  
  365. Node: a position on the board.
  366.  
  367. Major Node: a position on the board that always 
  368. connects in the direction of the owner's orientation.  (See 
  369. "maj" in the diagram)
  370.  
  371.  
  372. Minor Node: a position on the board that always 
  373. connects in the opposite direction of the owner's 
  374. orientation.  (See "min" in the diagram)
  375.  
  376.  
  377. Orientation:  the direction in which a player is trying to 
  378. connect nodes to win the game. The player who is trying 
  379. to connect top to bottom has the vertical orientation.  The 
  380. player who is trying to connect left to right has the 
  381. horizontal orientation.  
  382. The orientation does not refer to any specific node.  It only 
  383. refers to the players and the object of the game. 
  384.  
  385.  
  386. Owner:  the player who has placed a connector in a 
  387. node is the owner of that node.
  388.  
  389.  
  390. Path: a connected set of nodes owned by the same 
  391. player. The horizontal player owns two paths in the 
  392. diagram.
  393.  
  394.  
  395. Path Major Span: the number of major nodes spanned 
  396. by a path.  In the diagram, the horizontal player's path in 
  397. the upper-left hand corner has a major span of three.  The 
  398. horizontal player's other path has a major span of zero.  If 
  399. the vertical player moves in the major node highlighted in 
  400. purple, the Resultant Path will also have a major span of 
  401. three.
  402.  
  403.  
  404. Path Minor Span: the number of minor nodes spanned 
  405. by a path.   In the diagram, the horizontal player's path in 
  406. the upper-left hand corner has a minor span of 1.  The 
  407. horizontal player's other path also has a minor span of 1.
  408.  
  409.  
  410. Trial Node:  a single empty node that is the target of the 
  411. current weight evaluation during auto play.
  412.  
  413.  
  414. Resultant Path: the path that would be created if the 
  415. Trial Node were selected as the next move.  In the 
  416. diagram,  consider the "if vertical goes here" node as the 
  417. trial node.  The PathMajorSpan and PathMinorSpan 
  418. graphed in green is that of the resultant path. 
  419.  
  420. Real Path: a path that is already visible on the board.  
  421.  
  422.